One existing approach to providing push-to-talk (PTT) calls over Code Division Multiple Access (CDMA) systems, such as IS-2000 compliant systems, is to first establish a packet data connection and then send the PTT call control information over this data connection. However, this can be relatively slow since the originating mobile station (MS) must first be assigned a traffic channel (TCH) and then establish a data connection before its origination-side PTT call control information can be conveyed. Similarly, the MS targeted by the call is first paged, assigned a TCH, and then must establish a data connection before it can send its target-side PTT call control information or receive the origination-side call control information. This process, in which session establishment messages are sent after data connections have been established, can result in PTT call setup times of approximately 10-15 seconds. Many users are likely find such wait times for a service like PTT unacceptable. Accordingly, it would be highly desirable to have a method and apparatus providing substantially reduced PTT call setup delays.